package need_learn.coding.huawei;
/**
 * TODO 华为，约瑟夫问题  约瑟夫问题描述：编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3...这样依次报），
 *       数到 m 的 士兵会被杀死出列，之后的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。
 *       https://zhuanlan.zhihu.com/p/74436158 答案参考
 *       .12345
 *       12.45
 *       .245
 *       .24
 *       4
 * @author david
 * @version 1.0
 * @date 2021/4/20 14:56
 */
public class josephusProblem {


    public static void main(String[] args) {
        //单向环形链表解法
        System.out.println(solve(5, 3));
        //递归解法
        System.out.println(f(5, 3));
        //递归变形
        System.out.println(findTheWinner(5,3));
    }

    /**
     *     思路 n==1时 f(1,m)=1 所以找到 f(n,m) 与 f(n-1,m) 的关系就能解出本题
     *     假设 old 为删除之前的节点编号， new 为删除了一个节点之后的编号，
     *      old :        m-2   m-1  m  m+1  m+2
     *      new :        .		.	.	1	2
     *     	old的m+1对应new的1，所以old = (new + m - 1) % n + 1
     *     	则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。
     *     注：有些人可能会疑惑为什么不是 old = (new + m ) % n 呢？主要是因为编号是从 1 开始的，
     *      而不是从 0 开始的。如果 new + m == n的话，会导致最后的计算结果为 old = 0。
     *      所以 old = (new + m - 1) % n + 1. 这样，我们就得出 f(n, m) 与 f(n - 1, m)之间的关系了，
     *      而 f(1, m) = 1.所以我们可以采用递归的方式来做。代码如下：
     */
    static int f(int n, int m) {
        if (n == 1) return n;
        return (f(n - 1, m) + m - 1) % n + 1;
    }


    /**
     * f(1,3)：只有1个人了，那个人就是获胜者，他的下标位置是0
     * ●f ( 2 , 3 ) = ( f ( 1 , 3 ) + 3 ) % 2 = 3 % 2 = 1 在有2个人的时候，胜利者的下标位置为1
     * ●f ( 3 , 3 ) = ( f ( 2 , 3 ) + 3 ) % 3 = 4 % 3 = 1 在有3个人的时候，胜利者的下标位置为1
     * ●f ( 4 , 3 ) = ( f ( 3 , 3 ) + 3 ) % 4 = 4 % 4 = 0 在有4个人的时候，胜利者的下标位置为0
     * ●……
     * f● ( 11 , 3 ) = 6 f(11,3)=6f(11,3)=6
     *
     * 很神奇吧！现在你还怀疑这个公式的正确性吗？上面这个例子验证了这个递推公式的确可以计算出胜利者的下标，下面将讲解怎么推导这个公式。
     *
     * 问题1： 假设我们已经知道11个人时，胜利者的下标位置为6。那下一轮10个人时，胜利者的下标位置为多少？
     * 答： 其实吧，第一轮删掉编号为3的人后，之后的人都往前面移动了3位，胜利这也往前移动了3位，所以他的下标位置由6变成3。
     *
     * 问题2： 假设我们已经知道10个人时，胜利者的下标位置为3。那下一轮11个人时，胜利者的下标位置为多少？
     * 答： 这可以看错是上一个问题的逆过程，大家都往后移动3位，所以f ( 11 , 3 ) = f ( 10 , 3 ) + 3
     * 不过有可能数组会越界，所以最后模上当前人数的个数，f ( 11 , 3 ) = （ f ( 10 , 3 ) + 3 ） % 11
     *
     * 问题3： 现在改为人数改为N，报到M时，把那个人杀掉，那么数组是怎么移动的？
     * 答： 每杀掉一个人，下一个人成为头，相当于把数组向前移动M位。若已知N-1个人时，胜利者的下标位置位f ( N − 1 , M ) ，
     * 则N个人的时候，就是往后移动M为，(因为有可能数组越界，超过的部分会被接到头上，所以还要模N)，既f ( N , M ) = ( f ( N − 1 , M ) + M ) % n
     * 注：理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人，其实就是把这个数组向前移动了M位。然后逆过来，就可以得到这个递推式。
     * 因为求出的结果是数组中的下标，最终的编号还要加1
     **/
    static int findTheWinner(int n, int k) {
        int p = 0;
        for (int i = 2; i <= n; i++) {
            p = (p + k) % i;
        }
        return p + 1;
    }
    //单向环链表解法
    public static int solve(int n, int m) {
        if (m == 1 || n < 2) {
            return n;
        }
        //计数器减一，便于提升整体性能
        m = m - 1;
        System.out.println("" + m);
        // 创建环形链表
        Node head = createLinkedList(n);
        // 遍历删除
        int count = 0;
        Node cur = head;
        while (cur.next != cur) {
            count++;
            // 删除节点 点到谁 删掉谁后面的节点（原来应该报数的节点，在前面减掉了）
            if (count == m) {
                count = 0;
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        return cur.getDate();
    }

    static Node createLinkedList(int n) {
        Node head = new Node(1);
        Node next = head;
        for (int i = 2; i <= n; i++) {
            next.next = new Node(i);
            next = next.next;
        }
        // 头尾串联
        next.next = head;
        return head;
    }
}

//定义Node 节点
class Node {
    int date;
    Node next;

    public Node(int date) {
        this.date = date;
    }

    public int getDate() {
        return date;
    }
}


